﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/missing-number/
/*
题目描述：
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
*/

// 方法1——暴力法
/*
思路：
直接遍历0到n这n + 1个数字，对于每个数字都遍历一遍nums数组查看它是否存在
找到那个不存在的数字并返回。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int missingNumber1(int* nums, int numsSize) {
	assert(nums);
	int i = 0;
	int j = 0;
	for (i = 0; i <= numsSize; i++) {
		int flag = 0; // 表示是否找到i，找到为1，不找到为0，默认为0
		for (j = 0; j < numsSize; j++) {
			if (nums[j] == i) {
				flag = 1;
				break;
			}
		}
		if (0 == flag) {
			break;
		}
	}
	return i;
}
// 时间复杂度：O(n^2)，n为数组元素个数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——内层二分法
/*
思路：
在方法1的基础上，我们先对数组进行排序，在内层查找数字i是否存在时，使用二分法查找。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int cmp_int(const void* p1, const void* p2) {
	return *((int*)p1) - *((int*)p2);
}

int missingNumber2(int* nums, int numsSize) {
	assert(nums);
	int target = 0;
	int left = 0;
	int right = 0;
	int mid = 0;
	qsort(nums, numsSize, sizeof(nums[0]), cmp_int);
	for (target = 0; target <= numsSize; target++) {
		int flag = 0;
		left = 0;
		right = numsSize - 1;
		while (left <= right) {
			mid = left + (right - left) / 2;
			if (target < nums[mid]) {
				right = mid - 1;
			}
			else if (target > nums[mid]) {
				left = mid + 1;
			}
			else {
				flag = 1;
				break;
			}
		}
		if (0 == flag) {
			break;
		}
	}
	return target;
}
// 时间复杂度：O(N*log2N)，N为数组元素个数，我们最多要进行N + 1次二分查找，每次二分查找的复杂度为log2N，故时间复杂度为O(N*log2N)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。



// 方法3——求和法
/*
思路：
我们可以先求出从1到n所有数字的和SUM，再求出nums数组中所有数的和sum
用SUM 减去 sum得到的数即为丢失的数字。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int missingNumber3(int* nums, int numsSize) {
	assert(nums);
	int i = 0;
	int SUM = 0;
	int sum = 0;
	for (i = 1; i <= numsSize; i++) {
		SUM += i;
	}
	for (i = 0; i < numsSize; i++) {
		sum += nums[i];
	}
	return SUM - sum;
}
// 时间复杂度：O(n),n为数组元素个数，求SUM和sum都需要遍历n数字，故时间复杂度为O(n)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法4——排序后遍历
/*
思路：
我们对数组进行排序后，可以直接遍历查找，当发现nums[i + 1] - nums[i] > 1时，
则说明数组中缺少元素nums[i] + 1,直接返回nums[i] + 1即可。
只不过有两个特殊位置需要特殊判断：
如果nums[0] > 0，则说明数组中缺少的元素就是0，这时直接返回0即可。
如果nums[numsSize - 1] < numsSize，则说明数组中缺少的元素是numsSize(即n)，这时直接返回numsSize即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int missingNumber4(int* nums, int numsSize) {
	assert(nums);
	// 先对数组进行排序
	qsort(nums, numsSize, sizeof(nums[0]), cmp_int);
	// 特殊情况特殊处理
	if (nums[0] > 0) {
		return 0;
	}
	else if (nums[numsSize - 1] < numsSize) {
		return numsSize;
	}
	int i = 0;
	for (i = 0; i < numsSize - 1; i++) {
		if (nums[i + 1] - nums[i] > 1) {
			break;
		}
	}
	return nums[i] + 1;
}
// 时间复杂度：O(n)，n为数组元素个数，我们最多只需要遍历数组的n - 1个元素即可，股时间复杂度为O(n)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法5——位运算
/*
思路：
我们可以利用异或运算的特性：a ^ a = 0 来直接求出答案，
我们设数组arr中存放的是从0到n的n + 1个数字，我们在将数组nums中的元素全部异或在一起后
在追加异或上数组arr中的全部元素，则异或的最终结果就是那个丢失的数字，因为其他数字均在数组nums和数组arr中出现了一次
，共两次。而只有那个丢失的数字只在arr数组中出现了一次。
所以最终的结果为那个丢失的数字。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int missingNumber5(int* nums, int numsSize) {
	assert(nums);
	int ans = 0;
	int i = 0;
	// 先异或nums数组中的所有元素
	for (i = 0; i < numsSize; i++) {
		ans ^= nums[i];
	}
	// 再追加异或数字0到n
	for (i = 0; i <= numsSize; i++) {
		ans ^= i;
	}
	return ans;
}
// 时间复杂度：O(n)，n为数组元素个数，我们总共需要异或n + (n + 1)个数字，故时间复杂度为O(n)。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法6——数组模拟哈希表
/*
我们可以创建一个长度为n + 1的int数组has，并将其中元素全都初始化为-1。
然后遍历数组nums，将数组nums中的每一个元素都加入has数组中，然后遍历has数组
若has[i]还等于-1，则说明数字i并没有在数组nums中出现的，直接返回i即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int missingNumber6(int* nums, int numsSize) {
	assert(nums);
	int result = 0;
	// 模拟个has表
	int* has = (int*)malloc((numsSize + 1) * sizeof(int));
	if (NULL == has) {
		perror("missingNumber");
		return -1;
	}
	// 初始化
	int i = 0;
	for (i = 0; i <= numsSize; i++) {
		has[i] = -1;
	}
	for (i = 0; i < numsSize; i++) {
		has[nums[i]] = nums[i];
	}
	for (i = 0; i <= numsSize; i++) {
		if (-1 == has[i]) {
			result = i;
			break;
		}
	}
	free(has);
	has = NULL;
	return result;
}
// 时间复杂度：O(n)，n为数组元素个数，总时间约等于我们要遍历数组nums三次，故时间复杂度为O(n)。
// 空间复杂度：O(n)，我们需要用到n + 1个额外的整型空间，故空间空间复杂度为O(n)。

